The present invention relates to a cache memory unit, placed between processors and a main memory, for short-time storage to retain part of the contents of the main memory; and, more particularly, the invention relates to the cache memory unit that is so designed that specific lines are preferentially stored into the cache.
A cache is a faster-access memory of small capacity placed between a main memory and a processor that executes instructions read from the main memory. The cache is designed to temporarily retain the data in given units that the processor has fetched or retrieved through access to the main memory. Units of data to be stored into the cache are called blocks or cache lines. In the present Specification, the above units are simply referred to as lines.
The processor first accesses the cache to retrieve a line it needs. If the line exists on the cache (this result is called a hit), the processor uses it; otherwise, the processor accesses the main memory. The higher the cache hit rate, the more efficient will be the processing that can be performed. To increase the cache hit rate, it is necessary that lines more frequently accessed remain stored on the cache.
An analysis of patterns in which programs access the memory shows a general tendency: a spatial locality in that addresses near an accessed address are likely to be accessed before long; and a temporal locality in that the accessed address is likely to be accessed again before long. A typical known cache is designed to operate efficiently for programs having the above tendency. For such a cache, data access is performed in line units and data around the required data is stored together with the required data into the cache. Furthermore, in a cache using the LRU (Least Recently Used) method, a line that has been least recently accessed is replaced by a new line, so that recently accessed lines are not readily replaced.
However, the locality differs for different programs or different parts of a program. Data access in line units and line replacement by the LRU method do not always lead to an increase of the cache hit rate. This tendency is noticeable especially for business application programs.
One cause of the above problem is the storing of all lines equally into the cache. With the aim of solving this problem, some approaches have been disclosed that address this problem by preferential storing of specific lines into the cache, which contributes to enhancement of the cache performance. These approaches will be mentioned below.
In an approach described in U.S. Pat. No. 5,546,449 (this approach is hereinafter referred to as example 1), a specified line is inhibited from being replaced by another line.
In an approach described in Japanese Patent Laid-Open Publication No. 07-028706 (this approach is hereinafter referred to as example 2), priority ranks are assigned to lines when the lines are stored into the cache and a line of higher priority rank is inhibited from being replaced by a line of lower priority rank.
In an approach described in IA-64 Application Developer""s Architecture Guide, Intel, May (1999) pp. 4-20 to pp. 4-23 (this approach is hereinafter referred to as example 3), hint information is included in an instruction issued from a processor and a cache operation is controlled to store the line accessed by the instruction into a location of a certain level in the cache hierarchy, based on this information.
In an approach described in U.S. Pat. No. 5,787,490 (this approach is hereinafter referred to as example 4), every process is given a priority rank in the right to use the cache and the cache operation is controlled, based on this process-specific priority.
The above examples 1, 2, and 3 are, so to speak, methods in which different cache priority ranks are assigned to different lines. However, dynamic change in the way priority ranking is given to the lines is not taken into consideration.
On the other hand, as for the above example 4, it can be said that the priority is changed dynamically. However, the priority that can be changed in this example depends on the process for which a line is used.
Even in the same application, it is conceivable that the priority to be given to an individual line dynamically changes, depending on the load and use condition. Unless the cache executes line replacement control adaptive to the dynamic change of priority on a line-by-line basis, at present, there is a possibility of occurrence of undesirable line replacement, i.e., a line which is to preferentially remain stored on the cache is replaced by a lower priority line, which results in a condition in which the total cache hit rate cannot be increased sufficiently.
Accordingly, an object of the present invention is to provide a cache that enables a dynamic priority change on a per line basis so that the cache will preferentially retain higher priority lines and the cache hit rate will be increased, thereby providing for more efficient memory access.
Another object of the invention is to provide a cache memory unit applicable to an information processing system in which computer resources can be divided into a plurality of partitions and different applications can be run in different partitions, the cache enabling the user to specify lines to be handled preferentially and using an optimum method (policy) to store grouped lines into the cache per partition.
Another object of the invention is to provide a cache memory unit that achieves a higher cache hit rate than a typically known cache that handles lines equally, and which can be configured simply by modifying the system.
In the cache memory system configured according to a typical embodiment of the invention, a grouping method for dividing lines into groups is set into a table. Also, a storing policy for storing lines into the cache memory is defined for each of the groups set into the table. When an access command issued from a processor to access the main memory turns out to be a miss on the cache memory, the objective line is read from the main memory, and a line attribute of the objective line to which group the objective line belongs, in other words, is determined according to the table. Then, the objective line is stored into the cache memory according to control information of the cache memory and a storing policy of the corresponding group.
A detailed example of the configuration of the above-described cache memory system is as follows. The cache memory unit comprises a cache memory comprising a plurality of entries, each of which consists of a data area where a line is to be stored and a control information area where control information for the line is to be stored; a group definition controller that is used to divide lines that may be read by the processor from the main memory into groups and specify definitions of the groups; a group selector to determine one of the groups to which the line belongs in accordance with the group definitions and the information in a command issued from the processor to read data from the main storage; a policy definition controller that is used to assign a policy of storing whereby lines belonging the groups are stored into the cache memory; and a storing means to read a line from the main memory and store the line into the cache memory in accordance with the group to which the line belongs, the line control information retained in the cache memory for the candidate lines to be replaced, and the policy of storing, if a read request from the processor results in a miss.
In the foregoing examples, 1, 2, and 3, when a line is stored into the cache, if it is stored in accordance with the priority rank assigned to it at this point, this storing approach appears to be adaptive to a dynamic priority change. In the case of the examples 1 and 2, however, the priority rank of a line is recorded as control information into the cache memory when the line is stored into the cache. If, for example, a line L1 has priority P1 when it is stored into the cache, the priority P1 information is recorded into the cache memory together with the line L1 as the line L1 is stored. Even if the priority P1 of the line L1 is updated to a lower priority P1xe2x80x2 later, the cache memory retains the priority P1 information for the line L1 as is. Suppose that a new line L2 having priority L2 and the same index as the line L1 is stored into the cache and the priority ranking is P1xe2x80x2 less than P2 less than P1. At the point of storing the line L2, the priority P2 of the line L2 is higher than the priority P1xe2x80x2 of the line L1, and thus the line L1 should be replaced by the line L2. However, in actual practice, the line L2 is not stored into the cache, because a comparison is made between the old priority information P1 for the line L1, recorded in the cache, and the priority P2 of the line L2, and the priority of the line L1 is judged to be higher than that of the line L2.
In the case of the example 3, three levels of cache hierarchy are set: level 1 cache, level 2 cache, and level 3 cache. Four priority ranks are set: a line having a priority P1 is stored into the caches of all levels 1 to 3 of cache hierarchy; a line having a priority P2 is stored into the level 2 and level 3 caches only; a line having a priority P3 is stored into the level 3 cache only; and a line having a priority P4 is not stored into any level cache. The priority is used only when a line is stored into the cache. Suppose that the priority of a line L1 is P2 so that the line is stored in both level 2 and level 3 caches at a certain point in time. If the priority of the line L1 is updated to P3 later, the line L1 should be stored into the level 3 cache only. However, the previously stored line L1 remains stored in the level 2 cache, which affects the cache hit rate for other lines that are assigned priority P2 and are to be stored into the level 2 cache.
In another mode of embodying the invention, in addition to that described above, the line and group attribute definitions are separately assigned on a partition-by-partition basis and the cache memory units in each partition operate, based on the same definitions. Similarly, the policy of storing is separately assigned on a partition-by-partition basis and the cache memory units in each partition operate, based on the same policy.
Each time a change is made to the structure of the partitions of a computer system, the partition manager that is responsible for the management of the structure of the partitions will assign group definitions to the group definition tables for all cache memory units included in the partitions by means of the group definition controller. Similarly, the partition manager will assign a policy of storing to the policy tables for all cache memory units included in the partitions by means of the policy definition controller.
Furthermore, in another mode of embodying the invention, in addition to that described above, the group definition table contains data group and instruction group definitions; a line accessed as a result of the fact that the processor issues an instruction access command belongs to the instruction group and a line accessed as a result of the fact that the processor issues a data access command belongs to the data group. The group selector determines that the group to which a line belongs is the instruction group when the line is accessed due to the fact that the processor issues an instruction access command. The group selector determines that the group to which a line belongs is the data group when the line is accessed due to the fact that the processor issues a data access command.
Features of the present invention other than those described above will be disclosed in the following detailed description of the preferred embodiments.